Multiple transmit/multiple receive (MIMO) antennas may be used to enhance communication data rates in standards that allow more than one spatial stream to be transmitted, such as WLAN (IEEE 802.11n), WiMax (IEEE 802.16e), 3G-LTE, etc. FIG. 1 is a block diagram 30 of a multiple spatial stream transmitter configuration. Transmit data 32 is provided as a stream of 1's and 0's to an encoder 34. The encoder 34 encodes the transmit data 32 with, for example, an error correcting code. The output of the encoder 34 is provided to a spatial stream splitter 36, which divides the bit stream from the encoder 34 into two spatial streams in some order. The two spatial streams are then propagated to a frequency modulator 38 which modulates the streams into symbols, which may be represented as a sequence of complex numbers. The frequency modulated signals are sent through a transmission channel, such as through the air, via one or more antennas 40.
Efficient detection/equalization of the transmitted signals is central to a MIMO receiver. FIG. 2 is a block diagram of a multiple spatial stream receiver configuration. Multiple spatial stream signals are received, such as via one or more antennas 52, from the transmission channel. The received multiple spatial stream signals may be represented by the equation: yk=Hsk+w, where yk represents an N×1 vector of received signals over N spatial streams at time k, H is a complex-valued N×2 matrix that represents a channel matrix identifying the combined effects of the transmission channel and spatial mapping of the transmitter on the transmitted signal, xk is an N×1 vector that represents transmitted data values that are sought to be recovered, and w represents noise. The above relationship pertains to a single frequency in a frequency-flat fading single-carrier modulated system or, alternatively, applies to individual frequency subcarriers or tones in an orthogonal frequency division multiplexing (OFDM) or similarly modulated system. The received multiple spatial streams are propagated to an equalizer/receiver 54 which calculates log-likelihood ratios (LLR(1) and LLR(2)) for each of the received spatial streams. The calculated log-likelihood ratios are ordered and combined by a log-likelihood ratio combiner 56 and made available to a decoder 58. The decoder 58 decodes the data received from the combiner 56 and generates output data 60.
In a two spatial stream system, each data symbol received, xi, where i=1 corresponds to data transmitted on a first spatial stream, and i=2 corresponds to data transmitted on a second spatial stream, maps to n bits {b1(i), b2(i), . . . , bn(i)}. M=2n is the alphabet size of the underlying modulation, such as binary phase shift keying (BPSK), quadrature amplitude modulation (QAM), etc., and the set of all possible scalar constellation points may be represented by A. The log-likelihood ratio (LLR) for a bit bk(i) given a received vector y and a known channel matrix H may be represented as:
            L      ⁡              (                  b          k                      (            i            )                          )              =                  log        ⁢                              P            ⁡                          (                                                b                  k                                      (                    i                    )                                                  =                1                            )                                            P            ⁡                          (                                                b                  k                                      (                    i                    )                                                  =                0                            )                                          =              log        ⁢                  {                                    (                                                ∑                                      x                    ∈                                          x                                              k                        ,                        i                                                                                            ⁢                                  e                                                                                    -                                                                                                                                        y                              -                              Hx                                                                                                            2                                                                    /                      2                                        ⁢                                                                                  ⁢                                          σ                      2                                                                                  )                        /                          (                                                ∑                                      x                    ∈                                                                  x                        _                                                                    k                        ,                        i                                                                                                                                                    ⁢                                  e                                                                                    -                                                                                                                                        y                              -                              Hx                                                                                                            2                                                                    /                      2                                        ⁢                                                                                  ⁢                                          σ                      2                                                                                  )                                }                      ,where xk,i is the set of all possible x vectors with bk(i)=1, and xk,i is the set of all possible x vectors with bk(i)=0. In practice, the following simplification, called the Max-Log Approximation, is utilized:
      L    ⁡          (              b        k                  (          i          )                    )        ≈                    min                  x          ∈                      x                          k              ,              i                                          ⁢                                              y            -            Hx                                    2              -                  min                  x          ∈                                    x              _                                      k              ,              i                                          ⁢                                                              y              -              Hx                                            2                .            
There are several existing systems for detecting/equalizing received signals in multiple spatial stream systems. FIG. 3A is a block diagram 70 of a log-likelihood ratio calculator 72 that utilizes a linear equalizer 74. The linear equalizer 74 receives, via one or more antennas 76, a multi-spatial stream signal that has been transmitted through a channel and outputs a stream of log-likelihood ratios based on the received signals. For example, a zero-forcing equalizer is a linear equalizer that may be utilized, as illustrated in FIG. 3A. The zero-forcing equalizer seeks to recover the transmitted data values, xk, from the received signal, yk, that are modeled as, yk=Hxk+w, by assuming the noise vector is zero. Having a known channel effect matrix, H, enables calculation of data values, xk, to be recovered from the received signal, yk, as the data values are the only unknown remaining. While the zero-forcing equalizer has a simple design, the zeroing of the noise term makes the method prone to error as the noise term is almost certainly not zero in any real-world system.
FIG. 3B is a block diagram 80 of a log-likelihood ratio calculator 82 that utilizes a maximum-likelihood receiver 84. The maximum-likelihood receiver 84 receives a multi-spatial signal that has been transmitted through a channel, such as through the air, via one or more antennas 86, and outputs a stream of log-likelihood ratios based on the received signals. The maximum-likelihood receiver 84 is superior to most linear equalizers in error performance. However, maximum-likelihood receivers tend to be highly complex, such as having a complexity that grows exponentially with the number of spatial streams associated with the system.
FIG. 4A is a block diagram 100 of a maximum-likelihood receiver 102 that utilizes an exhaustive search methodology 104. The exhaustive search module 104 receives, via one or more antennas 106, a multi-spatial signal that has been transmitted through a channel and outputs a stream of log-likelihood ratios based on the received signals. In the exhaustive search methodology 104, the maximum likelihood receiver computes ∥y−Hx∥2 for all possible values of x. In a two spatial stream system, this results in M2 total distance computations. The maximum-likelihood receiver then computes log-likelihood ratios accordingly.
FIG. 4B is a diagram illustrating exemplary calculations for the exhaustive search methodology in a 4-QAM setting. A real/imaginary plot of a received signal is shown at 112. The exhaustive search methodology calculates the distance term, ∥y−Hx∥2, for each of the constellation points. FIG. 4B illustrates only six of the distance calculations 114 to six of the constellation points 116 for ease in viewing. However, the exhaustive search method would process distance calculations for all of the 16 constellation points resulting in 16 distance terms to be considered in calculating an LLR. This problem is further exacerbated in popular, more complex encoding schemes such as 16-QAM, which would require 256 distance calculations with 256 distance terms to be considered in calculating an LLR. This order M2, O(M2), complexity may introduce a significant bottleneck into the receiver system.
FIG. 5A is a block diagram 120 of a maximum-likelihood receiver 122 that utilizes a sphere decoding simplification 124. The sphere decoding methodology 124 receives a multi-spatial signal that has been transmitted through a channel, such as through the air, via one or more antennas 126, and outputs a stream of log-likelihood ratios based on the received signals. The sphere decoding methodology 124 seeks to simplify the complexity of the exhaustive search by limiting the amount of constellation points to which distance calculations are made and, consequently, the number of distance terms to be considered in calculating an LLR. FIG. 5B is a diagram 130 illustrating the sphere decoding simplification. In the sphere decoding technique, distance values, ∥y−Hx∥2, are only computed for those x such that Hx lies inside a sphere of radius D centered around the received signal, y (i.e., for x such that ∥y−Hx∥2≦D2). A real/imaginary plot of a received signal is shown at 132. As illustrated in FIG. 5B, the limitation of distance calculations 136 to constellation points 138 within a radius D 134 reduces the number of distance calculations and terms to be considered in LLR calculation to four. While this simplification may offer significant processing savings, it may have a detrimental effect on error performance. Because the set of constellation points 138 within radius D may not have constituent 1s and 0s at every bit location, as is evident in the first bit position where all four constellation points 138 contain ‘0’s at the first position, the LLR calculation formulas described above may have insufficient data to correctly calculate an LLR (e.g., the Max Log Approximation would not have any terms in xεxk,i from which to select a minimum).